import java.util.Arrays;

import lombok.extern.slf4j.Slf4j;

/**
 * 队列
 * @author zlzhangn
 */
@Slf4j
public class DataStructure_2_queue {
	
	/**
	 * 模拟循环队列（队列的顺序存储结构）
	 */
	public static class cycleQueue<T>{
		private int head = 0;	//队列头
		private int tail = 0;	//队列尾
		private final T[] tab;
		public cycleQueue(int length){
			tab = (T[]) new Object[length];
		}
		public void push(T t){
			if((tail+1)%tab.length==head){
				throw new RuntimeException("栈溢出");
			}
			tab[tail] = t;
			tail++;
			if(tail==tab.length)tail=0;
			log.info("{}入队, head:{} tail:{}, tab:{}",t,head,tail,Arrays.toString(tab));
		}
		public T pop(){
			T t = tab[head];
			tab[head] = null;
			head++;
			if(head==tab.length)head=0;
			log.info("{}出队, head:{} tail:{}, tab:{}",t,head,tail,Arrays.toString(tab));
			return t;
		}
		public int size(){
			int size = (tail+tab.length-head)%tab.length;
			log.info("队列长度：{}",(size==0&&head!=tail)?tab.length:size);
			return (size==0&&head!=tail)?tab.length:size;
		}
	}
	
	/**
	 * 链队列 
	 */
	public static class ChainQueue<T>{
		Node<T> node = new Node<T>();
		Node<T> head = node;
		Node<T> tail = node;
		int length = 0;
		class Node<T>{
			T t;
			Node<T> nextNode;
			public Node(){}
			public Node(T in) {
				t = in;
			}
		}
		public void push(T t){
			Node<T> node = new Node<T>(t);
			ChainQueue.this.node.nextNode = node;
			tail = node;
			length++;
			log.info("{}入队---{}",t,length);
		}
		public Node<T> take(){
			Node<T> node = ChainQueue.this.node;
			Node<T> result = new Node<T>(node.t);
			node = node.nextNode;
			head = node;
			length--;
			log.info("{}出队---{}",result,length);
			return result;
		}
	}
	
	public static void main(String[] args) {
		/*cycleQueue<Integer> cycleQueue = new cycleQueue<Integer>(5);
		cycleQueue.push(1);
		cycleQueue.push(2);
		cycleQueue.pop();
		cycleQueue.push(3);
		cycleQueue.push(3);
		cycleQueue.push(3);
		cycleQueue.size();
		cycleQueue.pop();
		cycleQueue.pop();
		cycleQueue.size();
		cycleQueue.push(4);*/
		ChainQueue<Integer> queue = new ChainQueue<Integer>();
		queue.push(1);
		queue.push(2);
		queue.take();
		queue.push(3);
	}

}
